#include "q3bsp.h"

#include "log.h"
#include "sys_image.h"
#include "render.h"

#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>


typedef unsigned char ubyte;

namespace 
{

inline void swizzle3(float* v)
{
	float temp = v[1];
	v[1] = v[2];
	v[2] = -temp;
}

inline void deswizzle3(float* v)
{
	v[0] = -v[0];
	float temp = v[1];
	v[1] = -v[2];
	v[2] = -temp;
}

inline void swizzle3(int* v)
{
	int temp = v[1];
	v[1] = v[2];
	v[2] = -temp;
}

enum Q3BSPDirectories
{
	BSPDir_Entities,
	BSPDir_Textures,
	BSPDir_Planes,
	BSPDir_Nodes,
	BSPDir_Leafs,
	BSPDir_LeafFaces,
	BSPDir_LeafBrushes,
	BSPDir_Models,
	BSPDir_Brushes,
	BSPDir_Brushsides,
	BSPDir_DrawVerts,
	BSPDir_DrawIndexes, 
	BSPDir_Effects,
	BSPDir_Faces,
	BSPDir_Lightmaps,
	BSPDir_Lightvols,
	BSPDir_Visdata,
	BSPDir_NUM,
};

//#pragma pack(push)
//#pragma pack(1)
struct Q3BSPHeader
{
	struct direntry
	{
		int		offset;
		int		len;
	};
	
	char		magic[4];
	int			version;
	direntry	dirs[BSPDir_NUM];
};

struct Q3BSPTexture
{
	char		name[64];
	int			flags;
	int			contents;
};

struct Q3BSPPlane
{
	float		normal[3];
	float		dist;
};

struct Q3BSPNode
{
	int			plane;
	int			children[2];
	int			min[3];
	int			max[3];
};

struct Q3BSPLeaf
{
	int			cluster;
	int			area;
	int			min[3];
	int			max[3];
	int			leafFace;
	int			numLeafFaces;
	int			leafBrush;
	int			numLeafBrushes;
};

struct Q3BSPLeafFace
{
	int			face;
};

struct Q3BSPVertex
{
	float		position[3];
	float		texcoord[2];
	float		lightmapCoord[2];
	float		normal[3];
	ubyte		colour[4];
};

enum Q3BSPFaceType
{
	FaceType_None,
	FaceType_Polygon,
	FaceType_Patch,
	FaceType_Mesh,
	FaceType_Billboard,
};

struct Q3BSPFace
{
	int			texture;
	int			effect;
	int			type;

	int			firstVertex;
	int			numVertices;

	int			firstIndex;
	int			numIndexes;
	
	int			lightmapIndex;
	int			lightmapX, lightmapY;
	int			lightmapWidth, lightmapHeight;

	float		lightmapPos[3];
	float		lightmapVectors[2][3];
	float		normal[3];
	int			patchWidth;
	int			patchHeight;
};

struct Q3BSPLightmap
{
	ubyte		lightmap[128][128][3];			// RGB
};

struct Q3BSPVisdata
{
	int			num;
	int			size;
};

// This isn't a lump in the BSP file, its constructed from the Entity lump
class Q3BSPEntity
{
public:

	Q3BSPEntity()
	{
		memset(className_, 0, 128);
		origin_[0] = origin_[1] = origin_[2] = 0.f;
	}

	Q3BSPEntity(const Q3BSPEntity& other)
	{
		assign(other);
	}

	Q3BSPEntity& operator=(const Q3BSPEntity& other)
	{
		if (this == &other)
		{
			return *this;
		}

		assign(other);
		return *this;
	}

	void assign(const Q3BSPEntity& other)
	{
		strncpy(className_, other.className_, 128);
		origin_[0] = other.origin_[0];
		origin_[1] = other.origin_[1];
		origin_[2] = other.origin_[2];
	}

	char		className_[128];
	float		origin_[3];
};

//#pragma pack(pop)



typedef std::map<Q3BSPFace*, std::vector<WorldSurface>> SurfaceCache;
SurfaceCache g_patchSurfaceCache;


}

class Q3BSP
{
public:

	Q3BSP(char* data)
		: header_(NULL)
		, entities_(NULL)
		, entitiesLen_(0)
		, textures_(NULL)
		, numTextures_(0)
		, nodes_(NULL)
		, numNodes_(0)
		, leafs_(NULL)
		, numLeafs_(0)
		, leafFaces_(NULL)
		, numLeafFaces_(0)
		, vertices_(NULL)
		, numVertices_(0)
		, indexes_(NULL)
		, numIndexes_(0)
		, lightmaps_(NULL)
		, numLightmaps_(0)
		, visdata_(NULL)
		, visVectors_(NULL)
		, data_(data)
	{
		if (data_ == NULL)
		{
			return;
		}

		header_ = reinterpret_cast<Q3BSPHeader*>(data_);
		
		Q3BSPHeader::direntry* dir = &header_->dirs[BSPDir_Nodes];
		nodes_ = reinterpret_cast<Q3BSPNode*>(data_ + dir->offset);
		numNodes_ = dir->len / sizeof(Q3BSPNode);
	
		dir = &header_->dirs[BSPDir_Entities];
		entities_ = reinterpret_cast<char*>(data_ + dir->offset);
		entitiesLen_ = dir->len;

		dir = &header_->dirs[BSPDir_Textures];
		textures_ = reinterpret_cast<Q3BSPTexture*>(data_ + dir->offset);
		numTextures_ = dir->len / sizeof(Q3BSPTexture);

		dir = &header_->dirs[BSPDir_Planes];
		planes_ = reinterpret_cast<Q3BSPPlane*>(data_ + dir->offset);
		numPlanes_ = dir->len / sizeof(Q3BSPPlane);

		dir = &header_->dirs[BSPDir_Leafs];
		leafs_ = reinterpret_cast<Q3BSPLeaf*>(data_ + dir->offset);
		numLeafs_ = dir->len / sizeof(Q3BSPLeaf);

		dir = &header_->dirs[BSPDir_LeafFaces];
		leafFaces_ = reinterpret_cast<Q3BSPLeafFace*>(data_ + dir->offset);
		numLeafFaces_ = dir->len / sizeof(Q3BSPLeafFace);

		dir = &header_->dirs[BSPDir_DrawVerts];
		vertices_ = reinterpret_cast<Q3BSPVertex*>(data_ + dir->offset);
		numVertices_ = dir->len / sizeof(Q3BSPVertex);

		dir = &header_->dirs[BSPDir_DrawIndexes];
		indexes_ = reinterpret_cast<int*>(data_ + dir->offset);
		numIndexes_ = dir->len / sizeof(int);

		dir = &header_->dirs[BSPDir_Faces];
		faces_ = reinterpret_cast<Q3BSPFace*>(data_ + dir->offset);
		numFaces_ = dir->len / sizeof(Q3BSPFace);

		dir = &header_->dirs[BSPDir_Lightmaps];
		lightmaps_ = reinterpret_cast<Q3BSPLightmap*>(data_ + dir->offset);
		numLightmaps_ = dir->len / sizeof(Q3BSPLightmap);

		dir = &header_->dirs[BSPDir_Visdata];
		visdata_ = reinterpret_cast<Q3BSPVisdata*>(data_ + dir->offset);
		visVectors_ = reinterpret_cast<ubyte*>(data_ + dir->offset + sizeof(Q3BSPVisdata));
	}

	bool Parse()
	{
		const bool magic =
			(header_->magic[0] == 'I') && 
			(header_->magic[1] == 'B') && 
			(header_->magic[2] == 'S') && 
			(header_->magic[3] == 'P');
		const bool fileIsValid = magic && header_->version == 0x2e;
		if (!fileIsValid)
		{
			return false;
		}

		entitiesParsed_.clear();
		Q3BSPEntity currentEntity;

		// TODO stop using strtok, clean this up
		std::vector<std::string> lines;
		char* line = strtok(entities_, "\n");
		while (line != NULL)
		{
			lines.push_back(std::string(line));
			line = strtok(NULL, "\n");
		}

		for (size_t i = 0; i < lines.size(); i++)
		{
			const std::string& line = lines.at(i);

			if (line == "{")
			{
				// start of new entity
				currentEntity = Q3BSPEntity();
			}
			else if (line == "}")
			{
				if (strlen(currentEntity.className_) == 0)
				{
					strcpy(currentEntity.className_, "globals");
				}

				// end of current entity
				entitiesParsed_.push_back(currentEntity);
			}
			else
			{
				const char* c = line.c_str();
				if (*c++ != '"')
				{
					Log_Printf("BSP Error: malformed entity defintion: '%s'\n", line);
					continue;
				}

				char key[128];
				int pos = 0;
				while (*c != '"' && pos < 128)
				{
					key[pos++] = *c++;
				}
				key[pos] = 0;

				c++;
				while (*c++ != '"')
				{
					;
				}

				char value[128];
				pos = 0;
				while (*c != '"' && pos < 128)
				{
					value[pos++] = *c++;
				}
				value[pos] = 0;

				if (strcmp(key, "classname") == 0)
				{
					const char* className = value;
					strncpy(currentEntity.className_, className, 128);
				}
				else if (strcmp(key, "origin") == 0)
				{
					const char* origin = value;
					int x, y, z;
					sscanf(origin, "%d %d %d", &x, &y, &z);
					currentEntity.origin_[0] = x;
					currentEntity.origin_[1] = y;
					currentEntity.origin_[2] = z;
					swizzle3(&currentEntity.origin_[0]);
				}
			}
		}

		Log_Printf("BSP: parsed %d entities\n", entitiesParsed_.size());
		Log_Printf("BSP: %d textures\n", numTextures_);

		std::map<int, int> referencedTextures;
		for (int i = 0; i < numFaces_; i++)
		{
			Q3BSPFace* face = &faces_[i];
			int count = 0;
			if (referencedTextures.find(face->texture) != referencedTextures.end())
			{
				count = referencedTextures[face->texture];
			}

			referencedTextures[face->texture] = count + 1;
		}

		for (std::map<int, int>::iterator iter = referencedTextures.begin(); iter != referencedTextures.end(); ++iter)
		{
		//	Log_Printf("Texture %d has %d references\n", iter->first, iter->second);
		}

		return true;
	}

	~Q3BSP()
	{
		delete[] data_;
	}

	Q3BSPHeader*	header_;

	char*			entities_;
	int				entitiesLen_;
	std::vector<Q3BSPEntity> entitiesParsed_;

	Q3BSPTexture*	textures_;
	int				numTextures_;

	Q3BSPPlane*		planes_;
	int				numPlanes_;

	Q3BSPNode*		nodes_;
	int				numNodes_;

	Q3BSPLeaf*		leafs_;
	int				numLeafs_;

	Q3BSPLeafFace*	leafFaces_;
	int				numLeafFaces_;

	Q3BSPVertex*	vertices_;
	int				numVertices_;

	int*			indexes_;
	int				numIndexes_;

	Q3BSPFace*		faces_;
	int				numFaces_;

	Q3BSPLightmap*	lightmaps_;
	int				numLightmaps_;

	Q3BSPVisdata*	visdata_;
	ubyte*			visVectors_;
	
	char*			data_;
};

int Q3BSP_FindLeaf(Q3BSP* bsp, float x, float y, float z)
{
	int index = 0;
	while (index >= 0)
	{
		Q3BSPNode* node = &bsp->nodes_[index];
		Q3BSPPlane* plane = &bsp->planes_[node->plane];

		const float distance = (x * plane->normal[0] + y * plane->normal[1] + z * plane->normal[2]) - plane->dist;
		if (distance >= 0)
		{
			index = node->children[0];
		}
		else
		{
			index = node->children[1];
		}
	}

	return -index - 1;
}

bool Q3BSP_IsClusterVisible(Q3BSP* bsp, int visCluster, int testCluster)
{
	if (visCluster < 0)
	{
		return true;
	}

	int i = (visCluster * bsp->visdata_->size) + (testCluster >> 3);
	ubyte visSet = bsp->visVectors_[i];
	return (visSet & (1 << (testCluster & 7))) != 0;
}



Q3BSP* Q3BSP_Load(const std::string& path)
{
	FILE* f = fopen(path.c_str(), "rb");
	if (f == NULL)
	{
		return NULL;
	}

	fseek(f, 0, SEEK_END);
	size_t fileSize = ftell(f);
	fseek(f, 0, SEEK_SET);

	char* buffer = new char[fileSize];
	memset(buffer, 0, fileSize);
	if (fread(buffer, sizeof(char), fileSize, f) != fileSize)
	{
		return NULL;
	}

	Q3BSP* bsp = new Q3BSP(buffer);
	if (!bsp->Parse())
	{
		delete bsp;
		bsp = NULL;
	}

	return bsp;
}

void Q3BSP_Release(Q3BSP** bsp)
{
	delete *bsp;
	*bsp = NULL;
}

void Q3BSP_GetStartPos(Q3BSP* bsp, float* x, float *y, float * z)
{
	*x = *y = *z = 0.f;

	for (size_t i = 0; i < bsp->entitiesParsed_.size(); i++)
	{
		const Q3BSPEntity& e = bsp->entitiesParsed_.at(i);

		if (strcmp(e.className_, "worldspawn") == 0)
		{
			continue;
		}

		if (strstr(e.className_, "info_player_intermission") != NULL)
		{
			*x = e.origin_[0];
			*y = e.origin_[1];
			*z = e.origin_[2];

			return;
		}
	}
}

void Q3BSP_GetVertexData(Q3BSP* bsp, SimpleVertex** worldVerts, int* numWorldVerts)
{
	*worldVerts = new SimpleVertex[bsp->numVertices_];
	*numWorldVerts = bsp->numVertices_;

	SimpleVertex* output = *worldVerts;
	Q3BSPVertex* input = bsp->vertices_;
	for (int i = 0; i < bsp->numVertices_; i++)
	{
		output = (*worldVerts) + i;
		input = bsp->vertices_ + i;

		output->Pos.x = input->position[0];
		output->Pos.y = input->position[1];
		output->Pos.z = input->position[2];
		output->Pos.w = 0.f;
		swizzle3(&output->Pos.x);
	//	Log_Printf("pos=%04.0f %04.0f %04.0f\n", output->Pos.x, output->Pos.y, output->Pos.z);

		// TODO quake3 seems to use the lightmap normal on the face for this?
	//	output->Norm.x = input->normal[0];
	//	output->Norm.y = input->normal[1];
	//	output->Norm.z = input->normal[2];
	//	swizzle3(&output->Norm.x);

		output->Tex.x = input->texcoord[0];
		output->Tex.y = input->texcoord[1];
		output->LightmapTex.x = input->lightmapCoord[0];
		output->LightmapTex.y = 1.f - input->lightmapCoord[1];

	//	output++;
	//	input++;
	}
}

void GenerateVertexDataForPatches(Q3BSPFace* face, int vertexOffset, int indexOffset, Q3BSPVertex* vertices, Q3BSPTexture* textures,
	SurfaceCache& cache, std::vector<SimpleVertex>& generatedVerts, std::vector<int>& generatedIndexes)
{
	const int L = 5;
	const int L1 = L + 1;
	const int numPatchVerts = L1 * L1;
	const int numPatches = ((face->patchWidth - 1) / 2) * ((face->patchHeight - 1) / 2);

	// WorldSurface.patchVerts is a fixed-size array so L being too high will cause a crash
	assert(numPatchVerts < MAX_PATCH_VERTS);

	std::vector<WorldSurface> patches;
	XMVECTOR outVerts[numPatchVerts];
	XMVECTOR outSt[numPatchVerts];
	XMVECTOR outLm[numPatchVerts];

	std::vector<int> subgridStartIndexes;

	// Each Q3BSPFace contains describes a number of bezier curves via 
	// a 2D grid of control point indexes. The grid has dimensions patchWidth x patchHeight,
	// with each patch represented by 3x3 sub-grid. The start of each sub-grid
	// is given by index (i, j) where i = [0, maxN) and j = [0, maxM)
	// see "Unoffical Quake 3 Map Specs" for more info
	const int maxN = (face->patchWidth-1) / 2;
	const int maxM = (face->patchHeight-1) / 2;
	for (int m = 0; m < maxM; m++)
	{
		for (int n = 0; n < maxN; n++)
		{
			// Flatten out the 2D (i, j) index to its 1D eqiuvalent
			const int offset = 2 * n + (face->patchWidth * (2 * m));
			subgridStartIndexes.push_back(offset);
		}
	}

	for (size_t j = 0; j < subgridStartIndexes.size(); j++)
	{
		const int offset = subgridStartIndexes.at(j);
		Q3BSPVertex* controlVerts = vertices + face->firstVertex;
		XMVECTOR controls[9];
		XMVECTOR st[9];
		XMVECTOR lm[9];

		std::vector<int> indexes;
		for (int w = 0; w < 3; w++)
		{
			for (int h = 0; h < 3; h++)
			{
				int index = ((face->patchWidth * w) + offset) + h;
				indexes.push_back(index);
			}
		}

		for (size_t i = 0; i < indexes.size(); i++)
		{
			const int index = indexes.at(i);
			const Q3BSPVertex* src = controlVerts + index;
			
			controls[i] = XMVectorSet(src->position[0],
				src->position[1], src->position[2], 0.f);

			st[i] = XMVectorSet(src->texcoord[0],
				src->texcoord[1], 0.f, 0.f);

			lm[i] = XMVectorSet(src->lightmapCoord[0],
				src->lightmapCoord[1], 0.f, 0.f);
		}

		for (int i = 0; i <= L; i++)
		{
			float a = (float)i / L;
			float b = 1.0 - a;

			outVerts[i] = XMVectorAdd( XMVectorScale(controls[0], (b * b)), 
				XMVectorAdd( XMVectorScale(controls[3], (2 * b * a)),
					XMVectorScale(controls[6], (a * a))));
			outSt[i] = XMVectorAdd( XMVectorScale(st[0], (b * b)), 
				XMVectorAdd( XMVectorScale(st[3], (2 * b * a)),
					XMVectorScale(st[6], (a * a))));
			outLm[i] = XMVectorAdd( XMVectorScale(lm[0], (b * b)), 
				XMVectorAdd( XMVectorScale(lm[3], (2 * b * a)),
					XMVectorScale(lm[6], (a * a))));
		}

		for (int i = 1; i <= L; i++)
		{
			float a = (float)i / L;
			float b = 1.0 - a;

			XMVECTOR temp[3];
			XMVECTOR tempSt[3];
			XMVECTOR tempLm[3];
			for (int j = 0; j < 3; j++)
			{
				int k = 3 * j;
				temp[j] = XMVectorAdd( XMVectorScale(controls[k + 0], (b * b)), 
					XMVectorAdd( XMVectorScale(controls[k + 1], (2 * b * a)),
					XMVectorScale(controls[k + 2], (a * a))));
				tempSt[j] = XMVectorAdd( XMVectorScale(st[k + 0], (b * b)), 
					XMVectorAdd( XMVectorScale(st[k + 1], (2 * b * a)),
					XMVectorScale(st[k + 2], (a * a))));
				tempLm[j] = XMVectorAdd( XMVectorScale(lm[k + 0], (b * b)), 
					XMVectorAdd( XMVectorScale(lm[k + 1], (2 * b * a)),
					XMVectorScale(lm[k + 2], (a * a))));
			}

			for (int j = 0; j <= L; j++)
			{
				float a = (float)j / L;
				float b = 1.0 - a;

				outVerts[i * L1 + j] = XMVectorAdd( XMVectorScale(temp[0], (b * b)), 
					XMVectorAdd( XMVectorScale(temp[1], (2 * b * a)),
					XMVectorScale(temp[2], (a * a))));
				outSt[i * L1 + j] = XMVectorAdd( XMVectorScale(tempSt[0], (b * b)), 
					XMVectorAdd( XMVectorScale(tempSt[1], (2 * b * a)),
					XMVectorScale(tempSt[2], (a * a))));
				outLm[i * L1 + j] = XMVectorAdd( XMVectorScale(tempLm[0], (b * b)), 
					XMVectorAdd( XMVectorScale(tempLm[1], (2 * b * a)),
					XMVectorScale(tempLm[2], (a * a))));
			}
		}

	//	generatedVerts.resize(numPatchVerts);
		const int firstPatchVert = generatedVerts.size();
		for (size_t i = 0; i < numPatchVerts; i++)
		{
			SimpleVertex vert;
			memset(&vert, 0, sizeof(SimpleVertex));

			vert.Pos.x = XMVectorGetX(outVerts[i]);
			vert.Pos.y = XMVectorGetY(outVerts[i]);
			vert.Pos.z = XMVectorGetZ(outVerts[i]);
			vert.Pos.w = 0.f;
			swizzle3(&vert.Pos.x);
		//	Log_Printf("%.1f %.1f %.1f\n", vert.Pos.x, vert.Pos.y, vert.Pos.z);

			vert.Tex.x = XMVectorGetX(outSt[i]);
			vert.Tex.y = XMVectorGetY(outSt[i]);

			vert.LightmapTex.x = XMVectorGetX(outLm[i]);
			vert.LightmapTex.y = 1.f - XMVectorGetY(outLm[i]);

			generatedVerts.push_back(vert);
		}

		WorldSurface surface;
		memset(&surface, 0, sizeof(surface));
		surface.type = Surface_Patch;
		assert(face->texture != -1);
		surface.texture = textures[face->texture].name;
		surface.lightmap = face->lightmapIndex;

//		surface.numPatchVerts = numPatchVerts;
		surface.firstVertex = firstPatchVert;

//		surface.numIndexes = L * L1 * 2;
//		surface.firstPatchIndex = generatedIndexes.size();
		surface.firstIndex = indexOffset + generatedIndexes.size();
		const int numTrianglesPerRow = L1 * 2;

//		generatedIndexes.resize(generatedIndexes.size() + surface.numIndexes);
		std::vector<int> genIndexes(L * L1 * 2);
		for (int row = 0; row < L; row++)
		{
			for (int col = 0; col <= L; ++col)
			{
				genIndexes[((row * L1 + col) * 2) + 1] = (row * L1 + col) + surface.firstVertex + vertexOffset;
				genIndexes[(row * L1 + col) * 2] = ((row + 1) * L1 + col) + surface.firstVertex + vertexOffset;
			}
		}

		{
		//	Log_Printf("stripIndexes=%u (%d tris)\n", genIndexes.size(), genIndexes.size() - 2);
		//	for (size_t stripIndex = 0; stripIndex < genIndexes.size(); stripIndex++)
		//	{
		//		Log_Printf("%d ", genIndexes[stripIndex]);
		//	}
		//	Log_Printf("\n");
		}

		// convert triange strip indexes to triangle list indexes
		std::vector<int> listIndexes;
		{
			bool flipWinding = false;
			for (size_t stripIndex = 2; stripIndex < genIndexes.size(); stripIndex++)
			{
				if ((stripIndex % numTrianglesPerRow == 0) ||
					((stripIndex-1) % numTrianglesPerRow == 0))
				{
					continue;
				}

				const int v0 = genIndexes[stripIndex - 2];
				const int v1 = genIndexes[stripIndex - 1];
				const int v2 = genIndexes[stripIndex - 0];

		//		Log_Printf("index=%d\n", stripIndex);
		//		Log_Printf("%d %d %d\n\n", v0, v1, v2);

				listIndexes.push_back(v0);
				if (!flipWinding)
				{
					listIndexes.push_back(v1);
					listIndexes.push_back(v2);
				}
				else
				{
					listIndexes.push_back(v2);
					listIndexes.push_back(v1);
				}

				flipWinding = !flipWinding;
			}
		}

	//	Log_Printf("listIndexes=%u\n", listIndexes.size());
	//	for (int i = 0; i < listIndexes.size() / 3; i++)
	//	{
	//		int index = i * 3;
	//		Log_Printf("%d %d %d\n", listIndexes[index+0], listIndexes[index+1], listIndexes[index+2]);
	//	}

		surface.numIndexes = listIndexes.size();
		assert(surface.numIndexes < MAX_INDEXES);
		for (int i = 0; i < surface.numIndexes; i++)
		{
			surface.indexes[i] = listIndexes[i];
		}

	//	generatedIndexes.insert(generatedIndexes.end(), genIndexes.begin(), genIndexes.end());
		generatedIndexes.insert(generatedIndexes.end(), listIndexes.begin(), listIndexes.end());

		patches.push_back(surface);
	}

	SurfaceCache::iterator faceIter = cache.find(face);
	assert(faceIter == cache.end());
	cache[face] = patches;
//	Log_Printf("patches=%u\n", patches.size());
}

void Q3BSP_GetPatchVertexData(Q3BSP* bsp, int vertexOffset, int indexOffset,
	SimpleVertex** patchVerts, int* numPatchVerts, 
	int** patchIndexes, int* numPatchIndexes)
{
	// Rather than re-generate the vertex and index data for each surface each frame,
	// pre-compure the data for all the patch surfaces, and lookup per frame
	// TODO support multiple tesselation levels for LOD?

	std::vector<SimpleVertex> verts;
	std::vector<int> indexes;

	g_patchSurfaceCache.clear();

	for (int i = 0; i < bsp->numFaces_; i++)
	{
		Q3BSPFace* f = bsp->faces_ + i;
		if (f->type != FaceType_Patch)
		{
			continue;
		}
		
		GenerateVertexDataForPatches(f, vertexOffset, indexOffset, bsp->vertices_, bsp->textures_, g_patchSurfaceCache, verts, indexes);
	}

	if (verts.size())
	{
		*patchVerts = new SimpleVertex[verts.size()];
		memcpy(*patchVerts, &verts[0], sizeof(SimpleVertex) * verts.size());
		*numPatchVerts = verts.size();

		*patchIndexes = new int[indexes.size()];
		memcpy(*patchIndexes, &indexes[0], sizeof(int) * indexes.size());
		*numPatchIndexes = indexes.size();
	}
}


void Q3BSP_GetIndexData(Q3BSP* bsp, int** worldIndices, int* numWorldIndices)
{
	*worldIndices = new int[bsp->numIndexes_];
	*numWorldIndices = bsp->numIndexes_;

	for (int i = 0; i < bsp->numIndexes_; i++)
	{
		(*worldIndices)[i] = bsp->indexes_[i];
	}
}

void Q3BSP_GetWorldSurfaceData(Q3BSP* bsp, SimpleVertex** worldVerts, int* numWorldVerts,
	int** worldIndexes, int* numIndexes)
{
	// TODO this is a mess!
	SimpleVertex* surfaceVerts = NULL;
	int numSurfVerts = 0;
	Q3BSP_GetVertexData(bsp, &surfaceVerts, &numSurfVerts);

	int* surfaceIndexes = NULL;
	int numSurfIndexes = 0;
	Q3BSP_GetIndexData(bsp, &surfaceIndexes, &numSurfIndexes);

	SimpleVertex* patchVerts = NULL;
	int* patchIndexes = NULL;
	int numPatchVerts = 0;
	int numPatchIndexes = 0;
	Q3BSP_GetPatchVertexData(bsp, numSurfVerts, numSurfIndexes, &patchVerts, &numPatchVerts, &patchIndexes, &numPatchIndexes);

	*worldVerts = new SimpleVertex[numSurfVerts + numPatchVerts];
	*numWorldVerts = numSurfVerts + numPatchVerts;
	memcpy(*worldVerts, surfaceVerts, sizeof(SimpleVertex) * (numSurfVerts));
	memcpy((*worldVerts) + numSurfVerts, patchVerts, sizeof(SimpleVertex) * (numPatchVerts));

	*worldIndexes = new int[numSurfIndexes + numPatchIndexes];
	*numIndexes = numSurfIndexes + numPatchIndexes;
	memcpy(*worldIndexes, surfaceIndexes, sizeof(int) * numSurfIndexes);
	memcpy((*worldIndexes) + numSurfIndexes, patchIndexes, sizeof(int) * numPatchIndexes);

	Log_Printf("surfVerts=%d surfIndexes=%d\n", numSurfVerts, numSurfIndexes);
	Log_Printf("patchVerts=%d patchIndexes=%d\n", numPatchVerts, numPatchIndexes);
	Log_Printf("worldVerts=%d worldIndexes=%d\n", *numWorldVerts, *numIndexes);

	delete[] surfaceVerts;
	delete[] surfaceIndexes;
	delete[] patchVerts;
	delete[] patchIndexes;
}

void Q3BSP_GetTexturePaths(Q3BSP* bsp, std::vector<std::string>& paths)
{
	paths.clear();
	for (int i = 0; i < bsp->numTextures_; i++)
	{
		Q3BSPTexture* t = &bsp->textures_[i];
	//	char pathBuffer[128];
	//	sprintf(pathBuffer, "data/baseq3/%s", t->name);
	//	paths.push_back(std::string(pathBuffer));
		paths.push_back(std::string(t->name));
	}
}

void AdjustForGamma(unsigned char* rgb)
{
	const int gamma = 2;
	unsigned char adjustedR = ((int)rgb[0]) << gamma;
	unsigned char adjustedG = ((int)rgb[1]) << gamma;
	unsigned char adjustedB = ((int)rgb[2]) << gamma;

	const int maxRGB = max(adjustedR, max(adjustedG, adjustedB));
	if (maxRGB > 255)
	{
		float factor = 255.f / (float)maxRGB;
		rgb[0] = (unsigned char)((float)adjustedR * factor);
		rgb[1] = (unsigned char)((float)adjustedG * factor);
		rgb[2] = (unsigned char)((float)adjustedB * factor);
	}
}

void Q3BSP_GetLightmapData(Q3BSP* bsp, std::vector<unsigned char*>& data, int* size)
{
	for (int i = 0; i < bsp->numLightmaps_; i++)
	{
		Q3BSPLightmap* l = &bsp->lightmaps_[i];

		unsigned char lm[128 * 128 * 3];
		memset(lm, 255, 128 * 128 * 3);

		unsigned char* pixeldata = lm;
		unsigned char* component = pixeldata;
		for (int j = 0; j < 128; j++)
		{
			for (int k = 0; k < 128; k++)
			{
				for (int c = 0; c < 3; c++)
				{
					const int rgba = (component - pixeldata) % 3;
					if (rgba < 3)
					{
						*component++ = l->lightmap[j][k][rgba];
					}
				}
			}
		}

		unsigned char* imageData = NULL;
		size_t imageSize = -1;
		if (!Sys_LightmapDataToImage(pixeldata, &imageData, &imageSize))
		{
			Log_Printf("Error: Failed to create lightmap image %d\n", i);
			imageData = NULL;
		}
		
		data.push_back(imageData);
		*size = imageSize;
	}
}

void BuildWorldSurfaceForFace_Polygon(Q3BSPFace* face, const int* indexes, Q3BSPTexture* textures)
{
	WorldSurface* surface = Render_AllocSurface();
	if (surface == NULL)
	{
		return;
	}

	memset(surface, 0, sizeof(surface));
	surface->type = Surface_TriangleList;
	assert(face->texture != -1);
	surface->texture = textures[face->texture].name;
	surface->lightmap = face->lightmapIndex;
	surface->numIndexes = face->numIndexes;
	surface->firstVertex = face->firstVertex;
	surface->firstIndex = face->firstIndex;
	
	for (int j = 0; j < face->numIndexes; j++)
	{
		surface->indexes[j] = face->firstVertex + indexes[face->firstIndex + j];
	}
}

void Q3BSP_GetWorldSurfacesForPosition(Q3BSP* bsp, float position[3])//, std::vector<WorldSurface>& worldSurfs)
{
//	worldSurfs.clear();

	// convert from world space into Q3 BSP space
	deswizzle3(position);

//	Log_Printf("pos=( %.0f, %.0f, %.0f )\n", position[0], position[1], position[2]);

	int visLeaf = Q3BSP_FindLeaf(bsp, position[0], position[1], position[2]);
	int visCluster = bsp->leafs_[visLeaf].cluster;
//	Log_Printf("leaf %d cluster %d\n", visLeaf, visCluster);
	
	static bool inited = false;
	static int s_prevCluster;
	if (!inited)
	{
		s_prevCluster = ~visCluster;
		inited = true;
	}

	if (s_prevCluster != visCluster)
	{
		Log_Printf("cluster %d\n", visCluster);
		s_prevCluster = visCluster;
	}

	std::set<int> visibleClusters;
	for (int i = 0; i < bsp->visdata_->num; i++)
	{
		if (Q3BSP_IsClusterVisible(bsp, visCluster, i))
		{
			visibleClusters.insert(i);
		}
	}

	std::vector<Q3BSPLeaf*> visibleLeafs;
	for (int i = 0; i < bsp->numLeafs_; i++)
	{
		Q3BSPLeaf* leaf = &bsp->leafs_[i];
		if (visibleClusters.find(leaf->cluster) != visibleClusters.end())
		{
			visibleLeafs.push_back(&bsp->leafs_[i]);
		}
	}

//	std::vector<int> visibleFaces;
	std::set<int> visibleFaces;
	for (size_t i = 0; i < visibleLeafs.size(); i++)
	{
		Q3BSPLeaf* leaf = visibleLeafs.at(i);
		const int start = leaf->leafFace;
		for (int j = 0; j < leaf->numLeafFaces; j++)
		{
			int leafFace = leaf->leafFace + j;
			int visibleFace = bsp->leafFaces_[leafFace].face;

			visibleFaces.insert(visibleFace);
		}
	}

	std::vector<int> vertexIndices;
	const auto end = visibleFaces.end();
	for (auto iter = visibleFaces.begin(); iter != end; ++iter)
	{
		Q3BSPFace* face = &bsp->faces_[*iter];

		if (face->firstVertex < 0 || face->firstVertex > bsp->numVertices_)
		{
			MessageBox(NULL, L"Bad index on face\n", L"Error", MB_OK | MB_SYSTEMMODAL);
			continue;
		}

		if (face->numIndexes > MAX_INDEXES)
		{
			MessageBoxA(NULL, "numIndexes > MAX_INDEXES", "Error", MB_OK | MB_SYSTEMMODAL);
			return;
		}

		switch (face->type)
		{
		case FaceType_Polygon:
		case FaceType_Mesh:
		{
		//	WorldSurface surface = BuildWorldSurfaceForFace_Polygon(face, bsp->indexes_);
		//	worldSurfs.push_back(surface);
			BuildWorldSurfaceForFace_Polygon(face, bsp->indexes_, bsp->textures_);
			
			break;
		}

		case FaceType_Patch:
		{
			std::vector<WorldSurface>& surfaces = g_patchSurfaceCache[face];
			for (auto i = surfaces.begin(); i != surfaces.end(); ++i)
			{
				WorldSurface* s = Render_AllocSurface();
				if (s != NULL)
				{
					*s = *i;
				}
			}

			break;
		}

		default:
			continue;
		}
	}
}
